[PROGRAMMERS] 블록 이동하기 - 2020 kakao recruitment
Posted on
문제 :
로봇개발자 “무지”는 한 달 앞으로 다가온 “카카오배 로봇경진대회”에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 “무지”는 “0”과 “1”로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 “0”은 빈칸을 “1”은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.
로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.
로봇은 다음과 같이 조건에 따라 회전이 가능합니다.
위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.
“0”과 “1”로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.
제한사항 :
- board의 한 변의 길이는 5 이상 100 이하입니다.
- board의 원소는 0 또는 1입니다.
- 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
풀이 :
방향 전환과 칸 이동하는 평범한 경로탐색 문제에서 경로 탐색 로봇이 하나의 칸만 차지하는 것이 아니라 두 칸을 차지하는 것으로 간단하게 문제가 바뀌었음에도 불구 매우 어렵게 다가왔다. 다른 블로그의 해설들에서는 더 좋은 풀이들이 많아 보여서 다음 번에 다른 방식으로도 문제를 풀어보고 다시 정리를 해볼까 싶다.
오늘은 내가 푼 방식으로 문제의 의도를 최대한 가깝게 파악해보려고 노력했다.
우선 이 문제가 기존의 경로 탐색보다 훨씬 어렵게 느껴지고 놓치기 쉬운 부분들을 오늘 몇 시간동안 고민해보며 정리해보았다.
- 경로 탐색 주체가 두칸을 차지하고 있기 때문에 우선 방향 전환의 두개의 축으로 시행될 수 있다. → 두개의 칸 각각에서 회전을 시켜보고 가능한 칸은 계속 탐색을 이어가야 했다.
- 무엇보다 두 칸을 기준으로 탐색하고 위치를 저장해야 했기 때문에 코드가 더러워지기 쉬움 → 하나의 칸을 기준으로 잡고 나머지 한 칸은 방향으로 표현하게 코드화 할려 했으나 오늘 내 머리로는 그게 훨씬 헷갈려 보여 그냥 두개의 칸을 모두 저장해서 탐색하는 방식을 택했음 → visit배열도 자연스럽게 4차원 배열로 만들었다.
- 두 칸을 모두 저장하고 탐색하는 방식을 택했기 때문에 visit배열을 체크할 때에도 나만의 방식으로 헷갈리지 않게 잘 체크해야 했다. → visit[first point x 좌표][first point y 좌표][second point x 좌표][second point y 좌표] 식으로 체크하게 되면 first point 와 second point가 순서가 바뀌어도 같은 위치에 로봇이 있는 것이기 때문에 두 경우 모두 visit check를 실행해주어야 한다. → 그렇지 않으면 중복된 위치를 두 번 읽는 경우가 생김.
코드 :
코드 보기/접기
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int di[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dj[8] = {1, 1, 0, -1, -1, -1, 0, 1};
typedef struct Qnode {
int firx, firy, secx, secy, cnt;
};
bool visit[100][100][100][100];
int solution(vector<vector<int>> board) {
int n = board.size() - 1, rotx, roty, revx, revy;
queue<Qnode> q;
q.push(Qnode{0, 0, 0, 1, 0});
visit[0][0][0][1] = true;
visit[0][1][0][0] = true;
while (!q.empty()) {
int curfx = q.front().firx, curfy = q.front().firy, cursx = q.front().secx, cursy = q.front().secy, curcnt = q.front().cnt;
q.pop();
if ((curfx == n && curfy == n) || (cursx == n && cursy == n)) return curcnt;
for (int k = 0; k < 8; k += 2) {
int cmpx1 = curfx + di[k], cmpy1 = curfy + dj[k], cmpx2 = cursx + di[k], cmpy2 = cursy + dj[k];
if (cmpx1 < 0 || cmpx2 < 0 || cmpy1 < 0 || cmpy2 < 0 || cmpx1 > n || cmpx2 > n || cmpy1 > n ||
cmpy2 > n || board[cmpx1][cmpy1] || board[cmpx2][cmpy2])
continue;
if (visit[cmpx1][cmpy1][cmpx2][cmpy2]) continue;
q.push(Qnode{cmpx1, cmpy1, cmpx2, cmpy2, curcnt + 1});
visit[cmpx1][cmpy1][cmpx2][cmpy2] = true;
visit[cmpx2][cmpy2][cmpx1][cmpy1] = true;
}
for (int num = 0; num < 2; num++) {
int curx = (num == 0) ? curfx : cursx, cury = (num == 0) ? curfy : cursy;
int partx = (num == 0) ? cursx : curfx, party = (num == 0) ? cursy : curfy;
for (int k = 0; k < 8; k += 2) {
bool isclock = true, iscounterclock = true;
int cmpx = curx + di[k], cmpy = cury + dj[k];
if (cmpx == partx && cmpy == party) {
for (int i = 1; i < 3; i++) {
rotx = curx + di[(k + i) % 8];
roty = cury + dj[(k + i) % 8];
revx = curx + di[(8 + k - i) % 8];
revy = cury + dj[(8 + k - i) % 8];
if (rotx < 0 || rotx > n || roty < 0 || roty > n || board[rotx][roty]) isclock = false;
if (revx < 0 || revx > n || revy < 0 || revy > n || board[revx][revy]) iscounterclock = false;
}
if (isclock && !visit[curx][cury][rotx][roty]) {
q.push(Qnode{curx, cury, rotx, roty, curcnt + 1});
visit[curx][cury][rotx][roty] = true;
visit[rotx][roty][curx][cury] = true;
}
if (iscounterclock && !visit[curx][cury][revx][revy]) {
q.push(Qnode{curx, cury, revx, revy, curcnt + 1});
visit[curx][cury][revx][revy] = true;
visit[revx][revy][curx][cury] = true;
}
}
}
}
}
}